home *** CD-ROM | disk | FTP | other *** search
/ MacWorld 1995 November / Macworld Nov ’95.toast / Developers / Advanced i⁄o / arithm_modadh.cc < prev    next >
Encoding:
Text File  |  1995-05-29  |  9.1 KB  |  289 lines  |  [TEXT/ALFA]
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /*
  3.  ************************************************************************
  4.  *
  5.  *                    Arithmetic Coding
  6.  *           Adaptive Histogram-based model for the data source
  7.  *
  8.  *
  9.  * The present file provides the functionality for both building the
  10.  * histogram for a sequence of integers items and supplying the
  11.  * arithmetic codec with probabilities of the items estimated from
  12.  * the histogram.
  13.  *
  14.  * The program uses the histogram to find out which symbols shall really
  15.  * come out and how frequent. It allocates frequency tables only for
  16.  * the symbols that really rather than potentially need to be coded.
  17.  * In all other respects (assuming Lorentzian-like initial probability
  18.  * distribution and tailoring as more symbols become known) the
  19.  * model behaves way the same as the simple AdaptiveModel does.
  20.  *
  21.  * $Id: arithm_modadh.cc,v 2.0 1995/02/07 19:37:03 oleg Exp oleg $
  22.  *
  23.  ************************************************************************
  24.  */
  25.  
  26. #ifdef __GNUC__
  27. #pragma implementation "arithm_modadh.h"
  28. #endif
  29.  
  30. #include "arithm_modadh.h"
  31. #include "std.h"
  32.  
  33.  
  34. /*
  35.  *========================================================================
  36.  *        Histogram-based Adaptive model for the data source
  37.  */
  38.  
  39.  
  40. /*
  41.  *------------------------------------------------------------------------
  42.  *            Constructors and Destructors
  43.  */
  44.  
  45.                 // Constructor
  46. AdaptiveHistModel::AdaptiveHistModel(const Histogram& histogram)
  47.      : no_distinct_symbols(histogram.no_distinct_symbols())
  48. {
  49.   assure(no_potential_symbols > 1,
  50.      "Bracketing interval for input symbols should include at least "
  51.      "two symbols");
  52.                  // Skip leading and tailing dummy symbols
  53.                  // (never occured in the histogram)
  54.   for(symbol_lwb=histogram.symbol_lwb;
  55.       symbol_lwb < histogram.symbol_upb && histogram.get(symbol_lwb) == 0;
  56.       symbol_lwb++)
  57.      ;
  58.      
  59.   for(symbol_upb=histogram.symbol_upb;
  60.       symbol_upb > symbol_lwb && histogram.get(symbol_upb) == 0;
  61.       symbol_upb--)
  62.      ;
  63.   assure( symbol_upb > symbol_lwb,
  64.         "there should be at least 2 symbols to code" );
  65.   no_potential_symbols = symbol_upb - symbol_lwb + 1;
  66.   assert( no_potential_symbols >= no_distinct_symbols );
  67.   allocate_model(no_distinct_symbols);
  68.   symbol_to_index = new Index[no_potential_symbols];
  69.   index_to_symbol = new Symbol[no_distinct_symbols];
  70.  
  71.   initialize_model(histogram);
  72. }
  73.  
  74.                 // Constructor for a dummy model. The real
  75.                 // model contents is supposed to be read
  76.                 // in later
  77. AdaptiveHistModel::AdaptiveHistModel(void)
  78.      : symbol_lwb(0), symbol_upb(0),
  79.        no_potential_symbols(0),
  80.        no_distinct_symbols(0)
  81. {
  82.   symbol_to_index = 0;
  83.   index_to_symbol = 0;
  84. }
  85.  
  86.                 // Destructor
  87. AdaptiveHistModel::~AdaptiveHistModel(void)
  88. {
  89.   assert( symbol_to_index != 0 && index_to_symbol != 0 );
  90.   delete [] symbol_to_index;
  91.   delete [] index_to_symbol;
  92. }
  93.  
  94. /*
  95.  *------------------------------------------------------------------------
  96.  *           Sort the histogram and set up the model
  97.  */
  98.  
  99. static struct Hist_elem 
  100.     { unsigned int count; Symbol symbol; }
  101. * Hist_sorted;
  102.  
  103.                 // Comparison routine to sort the Histogram
  104.                 // in the descending order
  105. static int hist_compar(const void * eli, const void * elj)
  106. {
  107.   if( ((const Hist_elem*)eli)->count < ((const Hist_elem*)elj)->count )
  108.     return 1;
  109.   else if( ((const Hist_elem*)eli)->count == ((const Hist_elem*)elj)->count )
  110.     return 0;
  111.   else
  112.     return -1;
  113. }
  114.  
  115. void AdaptiveHistModel::initialize_model(const Histogram& histogram)
  116. {
  117.   Hist_sorted = new Hist_elem[no_distinct_symbols];
  118.  
  119.   register Symbol symbol;
  120.   register int i;
  121.   for(symbol=histogram.symbol_lwb,i=0; symbol<=histogram.symbol_upb; symbol++)
  122.   {
  123.     unsigned int count = histogram.get(symbol);
  124.     if( count != 0 )
  125.       Hist_sorted[i].count = count, Hist_sorted[i].symbol = symbol, i++;
  126.   }
  127.   assert( i == no_distinct_symbols );
  128.  
  129.   qsort(Hist_sorted,no_distinct_symbols,sizeof(Hist_sorted[0]),hist_compar);
  130.  
  131.   memset(symbol_to_index,0,sizeof(symbol_to_index[0])*no_potential_symbols);
  132.   for(i=0; i<no_distinct_symbols; i++)
  133.   {
  134.     Index  index  = i+1;
  135.     Symbol symbol = Hist_sorted[i].symbol;
  136.     assert( symbol <= symbol_upb && symbol >= symbol_lwb );
  137.     symbol_to_index[symbol-symbol_lwb]  = index;
  138.     index_to_symbol[index-1] = symbol;
  139.   }
  140.   assert( i<EOF_index );
  141.  
  142.   initial_distribution();
  143. }
  144.  
  145.                 // Assign initial frequency counts
  146.                 // according to the Lorentzian ditribution
  147. void AdaptiveHistModel::initial_distribution(void)
  148. {
  149.   register int i;
  150.   cum_frequencies[no_indices] = 0;
  151.   for(i=no_indices; i>0; i--)
  152.   {
  153.     frequencies[i] = ( i == 1 ? 10*no_distinct_symbols : i <= 10 ? 10 : 1 );
  154.     cum_frequencies[i-1] = cum_frequencies[i] + frequencies[i];
  155.   }
  156.   frequencies[0] = 0;            // Must be zero to differ from freq[1]
  157. }
  158.  
  159. /*
  160.  *------------------------------------------------------------------------
  161.  *              Searching for index/symbol
  162.  */
  163.  
  164.                 // Return the index of a given symbol
  165. Index AdaptiveHistModel::get_index(const Symbol symbol) const
  166. {
  167.   if( symbol < symbol_lwb || symbol > symbol_upb )
  168.     _error("Symbol %d is out of interval [%d,%d]",
  169.        symbol, symbol_lwb, symbol_upb);
  170.   Index index = symbol_to_index[symbol-symbol_lwb];
  171.   if( index == 0 )
  172.     _error("\nSymbol %d has not been counted when Histogram was constructed",
  173.        symbol);
  174.   return index;
  175. }
  176.  
  177.                 // Return the symbol for a given index
  178. Symbol AdaptiveHistModel::get_symbol(const Index index) const
  179. {
  180.   if( index < 1 || index > no_indices || index == EOF_index )
  181.     _error("Index %d is out of boundaries [1,%d)",index,no_indices);
  182.   return index_to_symbol[index-1];
  183. }
  184.  
  185. /*
  186.  *------------------------------------------------------------------------
  187.  *           Input/Output for the frequency tables
  188.  * As a matter of fact, only  index_to_symbol[] table along with its size 
  189.  * needs to be saved. All other tables can easily be reconstructed from that.
  190.  *
  191.  * Thus, the format the tables are written is follows
  192.  *    short    no_distinct_symbols
  193.  *    short    index_to_symbol[0..no_distinct_symbols-1]
  194.  * The tables entries are coded using a variable bit size algorithm,
  195.  * see BitIn/BitOut for more details.
  196.  */
  197.  
  198. void AdaptiveHistModel::open(BitOut& file)
  199. {
  200.   file.write_short(no_distinct_symbols);
  201.   for(register int i=0; i<no_distinct_symbols; i++)
  202.     file.put_short(index_to_symbol[i]);
  203. }
  204.  
  205.                     // Read in the tables and set up
  206.                     // the model
  207. void AdaptiveHistModel::open(BitIn& file)
  208. {
  209.   no_distinct_symbols = file.read_short("Reading AdaptiveHistModel tables");
  210.   allocate_model(no_distinct_symbols);
  211.   index_to_symbol = new Symbol[no_distinct_symbols];
  212.  
  213.   for(register int i=0; i<no_distinct_symbols; i++)
  214.   {
  215.     const Symbol symbol = file.get_short();
  216.     if( i== 0 )
  217.       symbol_lwb = symbol_upb = symbol;
  218.     else
  219.       symbol_lwb = symbol_lwb > symbol ? symbol : symbol_lwb,
  220.       symbol_upb = symbol_upb < symbol ? symbol : symbol_upb;
  221.     index_to_symbol[i] = symbol;
  222.   }
  223.   
  224.   no_potential_symbols = symbol_upb - symbol_lwb + 1;
  225.   assert( no_potential_symbols > 1 );
  226.   assert( no_distinct_symbols <= no_potential_symbols );
  227.  
  228.   symbol_to_index = new Index[no_potential_symbols];
  229.  
  230.   memset(symbol_to_index,0,sizeof(symbol_to_index[0])*no_potential_symbols);
  231.   for(register Index index=1; index<=no_distinct_symbols; index++)
  232.   {
  233.     Symbol symbol = index_to_symbol[index-1];
  234.     symbol_to_index[symbol-symbol_lwb] = index;
  235.   }
  236.   
  237.   initial_distribution();
  238. }
  239.  
  240. /*
  241.  *------------------------------------------------------------------------
  242.  *            Update the adaptive model
  243.  *        to account for occurence of a particular index
  244.  */
  245.  
  246.                 // Scale the accumulated statistics down
  247.                 // in anticipation of a change, or simply to
  248.                 // keep counters from overflow
  249. void AdaptiveHistModel::scale_down_past(void)
  250. {
  251.   register int cum = 0;            // If so, halve all the counts
  252.   for(register int i=no_indices; i>=0; i--)
  253.   {                    // keeping them nonzero, and
  254.     cum_frequencies[i] = cum;        // recompute the cumulative counts
  255.     cum += (frequencies[i] = (frequencies[i]+1) >> 1);
  256.   }
  257. }
  258.  
  259. void AdaptiveHistModel::update_model(const Index index)
  260. {
  261.                     // See if freq counts near their max
  262.   if( total_cum_freq() >= Top_freq/2 )    // /2 makes rescaling work more often
  263.     scale_down_past();                    
  264.                     // Try to pull 'index' to the beginning
  265.                     // of the freq. table, skipping symbols
  266.                     // with the same freq.
  267.   register Lword * fp;
  268.   for(fp = &frequencies[index]; *fp == *(fp-1); fp--)
  269.     ;                    // Note, freq[0] never = freq[1]
  270.   Index new_index = fp - frequencies;    // Find a new position for the index
  271.   if( new_index < index )        // If the index is to move, update
  272.   {                    // the translation tables
  273.     Symbol symbol_oind = index_to_symbol[index-1];
  274.     Symbol symbol_nind = index_to_symbol[new_index-1];
  275.     index_to_symbol[index-1] = symbol_nind;
  276.     index_to_symbol[new_index-1] = symbol_oind;
  277.     symbol_to_index[symbol_oind-symbol_lwb] = new_index;
  278.     symbol_to_index[symbol_nind-symbol_lwb] = index;
  279.   }
  280.  
  281.                     // Note, the increment is large enough,
  282.   const int update_inc = no_indices/10 + 1; // to keep the realtive freq
  283.                     // during rescaling
  284.   frequencies[new_index] += update_inc;    // Increment the freq count for index
  285.   register Lword * cfp;            // And update the cumulative counts
  286.   for(cfp=&cum_frequencies[new_index]; cfp>&cum_frequencies[0]; )
  287.     *--cfp += update_inc;
  288. }
  289.